{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {
    "raw_mimetype": "text/restructuredtext"
   },
   "source": [
    ".. _nb_nsga2:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ".. meta::\n",
    "   :description: An implementation of the famous NSGA-II (also known as NSGA2) algorithm to solve multi-objective optimization problems. The non-dominated rank and crowding distance is used to introduce diversity in the objective space in each generation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ".. meta::\n",
    "   :keywords: NSGA2, NSGA-II, Non-Dominated Sorting, Multi-objective Optimization, Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "# NSGA-II: Non-dominated Sorting Genetic Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The algorithm is implemented based on <cite data-cite=\"nsga2\"></cite>.\n",
    "The algorithm follows the general outline of a genetic algorithm with a modified mating and survival selection. In NSGA-II, first, individuals\n",
    "are selected frontwise. By doing so, there will be the situation where a front needs to be split because not all individuals are allowed to survive. In this splitting front, solutions are selected based on crowding distance. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align: center;\">\n",
    "    <img src=\"https://github.com/anyoptimization/pymoo-data/blob/main/docs/images/nsga2_crowding.png?raw=true\" width=\"350\">\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "The crowding distance is the Manhatten Distance in the objective space. However, the extreme points are desired to be kept every generation and, therefore, get assigned a crowding distance of infinity."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align: center;\">\n",
    "    <img src=\"https://github.com/anyoptimization/pymoo-data/blob/main/docs/images/nsga2_survival.png?raw=true\" width=\"500\">\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Furthermore, to increase some selection pressure, NSGA-II uses a binary tournament mating selection. Each individual is first compared by rank and then crowding distance. There is also a variant in the original C code where instead of using the rank, the domination criterium between two solutions is used."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from pymoo.algorithms.moo.nsga2 import NSGA2\n",
    "from pymoo.problems import get_problem\n",
    "from pymoo.optimize import minimize\n",
    "from pymoo.visualization.scatter import Scatter\n",
    "\n",
    "problem = get_problem(\"zdt1\")\n",
    "\n",
    "algorithm = NSGA2(pop_size=100)\n",
    "\n",
    "res = minimize(problem,\n",
    "               algorithm,\n",
    "               ('n_gen', 200),\n",
    "               seed=1,\n",
    "               verbose=False)\n",
    "\n",
    "plot = Scatter()\n",
    "plot.add(problem.pareto_front(), plot_type=\"line\", color=\"black\", alpha=0.7)\n",
    "plot.add(res.F, facecolor=\"none\", edgecolor=\"red\")\n",
    "plot.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Moreover, we can customize NSGA-II to solve a problem with binary decision variables, for example, ZDT5."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from pymoo.algorithms.moo.nsga2 import NSGA2\n",
    "from pymoo.problems import get_problem\n",
    "from pymoo.operators.crossover.pntx import TwoPointCrossover\n",
    "from pymoo.operators.mutation.bitflip import BitflipMutation\n",
    "from pymoo.operators.sampling.rnd import BinaryRandomSampling\n",
    "from pymoo.optimize import minimize\n",
    "from pymoo.visualization.scatter import Scatter\n",
    "\n",
    "problem = get_problem(\"zdt5\")\n",
    "\n",
    "algorithm = NSGA2(pop_size=100,\n",
    "                  sampling=BinaryRandomSampling(),\n",
    "                  crossover=TwoPointCrossover(),\n",
    "                  mutation=BitflipMutation(),\n",
    "                  eliminate_duplicates=True)\n",
    "\n",
    "res = minimize(problem,\n",
    "               algorithm,\n",
    "               ('n_gen', 500),\n",
    "               seed=1,\n",
    "               verbose=False)\n",
    "\n",
    "Scatter().add(res.F).show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### API"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "raw_mimetype": "text/restructuredtext"
   },
   "source": [
    ".. autoclass:: pymoo.algorithms.moo.nsga2.NSGA2\n",
    "    :noindex:"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
